Intermediate-representation recovery from low-level code

ABSTRACT

The goal of our work is to create tools that an analyst can use to understand the workings of COTS components, plugins, mobile code, and DLLs, as well as memory snapshots of worms and virus-infected code. This paper describes how static analysis provides techniques that can be used to recover intermediate representations that are similar to those that can be created for a program written in a high-level language.

References

1. PREfast with driver-specific rules, October 2004. WHDC, Microsoft Corp., http://www.microsoft.com/whdc/devtools/tools/PREfastdrv.mspx.]]
2. W. Amme. P. Braun, E. Zehendner, and F. Thomasset. Data dependence analysis of assembly code. Int. J. Parallel Proc., 2000.]]
3. W. Backes. Programmanalyse des XRTL Zwischencodes. PhD thesis, Universitaet des Saarlandes, 2004. (In German.).]]
4. G. Balakrishnan and T. Reps. Analyzing memory accesses in x86 executables. In CC, 2004.]]
5. G. Balakrishnan and T. Reps. Recency-abstraction for heap-allocated storage. TR 1548, UW-Madison, December 2005.]]
6. G. Balakrishnan and T. Reps. Recovery of variables and heap structure in x86 executables. TR 1533, UW-Madison, 2005.]]
7. G. Balakrishnan, T. Reps, D. Melski, and T. Teitelbaum. WYSINWYX: What You See Is Not What You eXecute. In VSTTE, 2005.]]
8. T. Ball and S. K. Rajamani. The SLAM toolkit. In CAV., 2001.]]
9. J. Bergeron, M. Debbabi, J. Desharnais, M. M. Erhioui, Y. Lavoie, and N. Tawbi. Static detection of malicious code in executable programs. Int. J. of Req. Eng., 2001.]]
10. J. Bergeron, M. Debbabi, M. M. Erhioui, and B. Ktari. Static analysis of binary code to isolate malicious behaviors. In WETICE, 1999.]]
11. A. Bouajjani, J. Esparza, and T. Touili. A generic approach to the static analysis of concurrent programs with procedures. In POPL, 2003.]]
12. W. Bush, J. Pincus, and D. Sielaff. A static analyzer for finding dynamic programming errors. S-P&E, 30, 2000.]]
13. H. Chen, D. Dean, and D. Wagner. Model checking one million lines of C code. In NDSS, 2004.]]
14. H. Chen and D. Wagner. MOPS: An infrastructure for examining security properties of software. In CCS, 2002.]]
15. C. Cifuentes and A. Fraboulet. Interprocedural data flow recovery of high-level language code from assembly. TR 421, U. Queensland, 1997.]]
16. C. Cifuentes and A. Fraboulet. Intraprocedural static slicing of binary executables. In ICSM, 1997.]]
17. C. Cifuentes, D. Simon, and A. Fraboulet. Assembly to high-level language translation. In ICSM, 1998.]]
18. CodeSurfer, GrammaTech, Inc. "http://www.grammatech.com".]]
19. K. D. Cooper and K. Kennedy. Interprocedural side-effect analysis in linear time. In PLDI, 1988.]]
20. J. C. Corbett, M. B. Dwyer, J. Hatcliff, S. Laubach, C. S. Pasareanu, Robby, and H. Zheng. Bandera: Extracting finite-state models from Java source code. In ICSE, 2000.]]
21. P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction of approximation of fixed points. In POPL, 1977.]]
22. M. Das, S. Lerner, and M. Seigle. ESP: Path-sensitive program verification in polynomial time. In PLDI, 2002.]]
23. S. K. Debray, R. Muth, and M. Weippert. Alias analysis of executable code. In POPL, 1998.]]
24. P. H. Eidorff, F. Henglein, C. Mossin, H. Niss, M. H. Sørensen, and M. Tofte. Anno Domini: From type theory to year 2000 conversion tool. In POPL, 1999.]]
25. D. R. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In OSDI. 2000.]]
26. B. Guo. M. J. Bridges, S. Triantafyllis, G. Ottoni, F. Raman, and D. I. August. Practical and accurate low-level pointer analysis. In 3nd Int. Symp. on Code Gen. and Opt., pages 291--302, 2005.]]
27. K. Havelund and T. Pressburger. Model checking Java programs using Java PathFinder. STTT, 2(4), 2000.]]
28. T. A. Henzinger, R. Jhala, R. Majumdar, and G. Sutre. Lazy abstraction. In POPL, 2002.]]
29. S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. TOPLAS, 12(1):26--60, January 1990.]]
30. M. Howard. Some bad news and some good news. October 2002. MSDN, Microsoft Corp.]]
31. IDAPro disassembler, http://www.datarescue.com/idabase/.]]
32. N. Kidd, T. Reps, D. Melski, and A. Lal. WPDS++; A C++ library for weighted pushdown systems, 2004. http://www.cs.wisc.edu/wpis/wpds++/.]]
33. A. Lal, T. Reps, and G. Balakrishnan. Extended weighted pushdown systems. In CAV, 2005.]]
34. J. R. Larus and E. Schnarr. EEL: Machine-independent executable editing. In PLDI, 1995.]]
35. M. Müller-Olm and H. Seidl. Analysis of modular arithmetic. In ESOP, 2005.]]
36. A. Mycroft. Type-based decompilation. In ESOP, 1999.]]
37. G. Ramalingam, J. Field, and F. Tip. Aggregate structure identification and its application to program analysis. In POPL, 1999.]]
38. T. Reps, G. Balakrishnan, J. Lim, and T. Teitelbaum. A next-generation platform for analyzing executables. In APLAS, 2005.]]
39. T. Reps, S. Schwoon, and S. Jha. Weighted pushdown systems and their application to interprocedural dataflow analysis. In SAS, 2003.]]
40. T. Reps, S. Schwoon. S. Jha, and D. Melski. Weighted pushdown systems and their application to interprocedural dataflow analysis. SCP, 58(1--2):206--263, October 2005.]]
41. X. Rival. Abstract interpretation based certification of assembly code. In VMCAI, 2003.]]
42. M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In Program Flow Analysis: Theory and Applications, chapter 7. Prentice-Hall, Englewood Cliffs, NJ, 1981.]]
43. A. Srivastava, A. Edwards, and H. Vo. Vulcan: Binary transformation in a distributed environment. TR 2001--50, Microsoft Research, 2001.]]
44. A. Srivastava and A. Eustace. ATOM - A system for building customized program analysis tools. In PLDI, 1994.]]
45. D. Wagner, J. Foster, E. Brewer, and A. Aiken. A first step towards automated detection of buffer overrun vulnerabilities. In NDSS, 2000.]]
46. D. W. Wall. Systems for late code modification. In R. Giegerich and S. L. Graham, editors, Code Generation - Concepts. Tools, Techniques, pages 275--293. Springer-Verlag, 1992.]]
47. H. S. Warren, Jr. Hacker's Delight. Addison-Wesley, 2003.]]
48. R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In PLDI, 1995.]]

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Verification

• Software and its engineering

  • Software creation and management

    • Software development process management

    • Software verification and validation

      • Formal software verification

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Software verification

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

      • Program verification

    • Program semantics